Robust Computations with Dynamical Systems
Identifieur interne : 003032 ( Main/Exploration ); précédent : 003031; suivant : 003033Robust Computations with Dynamical Systems
Auteurs : Olivier Bournez [France] ; Daniel S. Graça [Portugal] ; Emmanuel Hainry [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
English descriptors
Abstract
Abstract: In this paper we discuss the computational power of Lipschitz dynamical systems which are robust to infinitesimal perturbations. Whereas the study in [1] was done only for not-so-natural systems from a classical mathematical point of view (discontinuous differential equation systems, discontinuous piecewise affine maps, or perturbed Turing machines), we prove that the results presented there can be generalized to Lipschitz and computable dynamical systems. In other words, we prove that the perturbed reachability problem (i.e. the reachability problem for systems which are subjected to infinitesimal perturbations) is co-recursively enumerable for this kind of systems. Using this result we show that if robustness to infinitesimal perturbations is also required, the reachability problem becomes decidable. This result can be interpreted in the following manner: undecidability of verification doesn’t hold for Lipschitz, computable and robust systems. We also show that the perturbed reachability problem is co-r.e. complete even for C ∞ -systems.
Url:
DOI: 10.1007/978-3-642-15155-2_19
Affiliations:
- France, Portugal
- Grand Est, Lorraine (région), Île-de-France
- Nancy, Palaiseau, Vandœuvre-lès-Nancy
- Nancy-Université
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003769
- to stream Istex, to step Curation: 003726
- to stream Istex, to step Checkpoint: 000794
- to stream Hal, to step Corpus: 004247
- to stream Hal, to step Curation: 004247
- to stream Hal, to step Checkpoint: 002404
- to stream Main, to step Merge: 003089
- to stream Main, to step Curation: 003032
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Robust Computations with Dynamical Systems</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name></author><author><name sortKey="Graca, Daniel S" sort="Graca, Daniel S" uniqKey="Graca D" first="Daniel S." last="Graça">Daniel S. Graça</name></author><author><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:E84AE80BB364541F870FD6ADE2CE20D47903D3BF</idno><date when="2010" year="2010">2010</date><idno type="doi">10.1007/978-3-642-15155-2_19</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-JSV52WC9-2/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003769</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003769</idno><idno type="wicri:Area/Istex/Curation">003726</idno><idno type="wicri:Area/Istex/Checkpoint">000794</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000794</idno><idno type="wicri:doubleKey">0302-9743:2010:Bournez O:robust:computations:with</idno><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00522029</idno><idno type="url">https://hal.inria.fr/inria-00522029</idno><idno type="wicri:Area/Hal/Corpus">004247</idno><idno type="wicri:Area/Hal/Curation">004247</idno><idno type="wicri:Area/Hal/Checkpoint">002404</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">002404</idno><idno type="wicri:Area/Main/Merge">003089</idno><idno type="wicri:Area/Main/Curation">003032</idno><idno type="wicri:Area/Main/Exploration">003032</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Robust Computations with Dynamical Systems</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Ecole Polytechnique, LIX, 91128, Palaiseau Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Palaiseau</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Graca, Daniel S" sort="Graca, Daniel S" uniqKey="Graca D" first="Daniel S." last="Graça">Daniel S. Graça</name><affiliation wicri:level="1"><country xml:lang="fr">Portugal</country><wicri:regionArea>DM/FCT, Universidade do Algarve, C. Gambelas, 8005-139, Faro</wicri:regionArea><wicri:noRegion>Faro</wicri:noRegion></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Portugal</country><wicri:regionArea>SQIG/Instituto de Telecomunicações, Lisbon</wicri:regionArea><wicri:noRegion>Lisbon</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Portugal</country></affiliation></author><author><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>LORIA, BP 239, 54506, Vandœuvre-lès-Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName></affiliation><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Nancy Université, Université Henri Poincaré, Nancy</wicri:regionArea><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName><orgName type="university">Nancy-Université</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>analog computation</term><term>computable analysis</term><term>model-checking</term><term>verification</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper we discuss the computational power of Lipschitz dynamical systems which are robust to infinitesimal perturbations. Whereas the study in [1] was done only for not-so-natural systems from a classical mathematical point of view (discontinuous differential equation systems, discontinuous piecewise affine maps, or perturbed Turing machines), we prove that the results presented there can be generalized to Lipschitz and computable dynamical systems. In other words, we prove that the perturbed reachability problem (i.e. the reachability problem for systems which are subjected to infinitesimal perturbations) is co-recursively enumerable for this kind of systems. Using this result we show that if robustness to infinitesimal perturbations is also required, the reachability problem becomes decidable. This result can be interpreted in the following manner: undecidability of verification doesn’t hold for Lipschitz, computable and robust systems. We also show that the perturbed reachability problem is co-r.e. complete even for C ∞ -systems.</div></front></TEI><affiliations><list><country><li>France</li><li>Portugal</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Île-de-France</li></region><settlement><li>Nancy</li><li>Palaiseau</li><li>Vandœuvre-lès-Nancy</li></settlement><orgName><li>Nancy-Université</li></orgName></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name></region><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name></country><country name="Portugal"><noRegion><name sortKey="Graca, Daniel S" sort="Graca, Daniel S" uniqKey="Graca D" first="Daniel S." last="Graça">Daniel S. Graça</name></noRegion><name sortKey="Graca, Daniel S" sort="Graca, Daniel S" uniqKey="Graca D" first="Daniel S." last="Graça">Daniel S. Graça</name><name sortKey="Graca, Daniel S" sort="Graca, Daniel S" uniqKey="Graca D" first="Daniel S." last="Graça">Daniel S. Graça</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003032 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003032 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:E84AE80BB364541F870FD6ADE2CE20D47903D3BF
|texte= Robust Computations with Dynamical Systems
}}
| This area was generated with Dilib version V0.6.33. |  |